package com.acwing.partition12;

import java.io.*;
import java.util.ArrayList;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/12/31 22:48
 */
public class AC1118分成互质组 {

    private static final int N = 12;
    private static int n = 0, answer = N;
    private static int[] nums = new int[N];
    private static boolean[] visited = new boolean[N];
    //存放每个组的元素
    private static List<List<Integer>> groupList = new ArrayList<>(N);

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(reader.readLine());
        String[] s = reader.readLine().split("\\s+");
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(s[i]);
            groupList.add(new ArrayList<>());
        }
        dfs(0, 1, 0, 0);
        writer.write(answer + "\n");
        writer.flush();
    }

    private static void dfs(int groupId, int groupSize, int count, int start) {
        if (groupSize >= answer) return;
        if (count == n) {
            answer = groupSize;
            return;
        }
        boolean flag = false;
        //以组合的方式进行搜索
        for (int i = start; i < n; i++) {
            if (!visited[i] && check(groupId, nums[i])) {
                //尝试将nums[i]放入当前组
                visited[i] = true;
                groupList.get(groupId).add(nums[i]);
                dfs(groupId, groupSize, count + 1, i + 1);
                //回溯
                visited[i] = false;
                flag = true;
                groupList.get(groupId).remove(groupList.get(groupId).size() - 1);
            }
            //第一个数必定被放入了一组，而组与组之间是没有区别的。比如对于数据3，7，6，14来说，第一次搜索结束后{3, 14}, {7，6}被找到，
            //后续是不需要找{7, 6}, {14, 3}的，所以可以直接返回。
            if (groupId == 0 && start == 0) return;
        }
        //如果当前这个nums[i]不能放入groupId这个组中，就新开一个组，并从开始再搜索一遍
        if (!flag) dfs(groupId + 1, groupSize + 1, count, 0);
    }

    private static int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }

    private static boolean check(int groupId, int num) {
        List<Integer> group = groupList.get(groupId);
        for (int i = 0; i < group.size(); i++) {
            if (gcd(group.get(i), num) > 1) return false;
        }
        return true;
    }
}
